// https://leetcode.cn/problems/recover-binary-search-tree/
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
#include <iostream>
#include <vector>


using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode *pre;
    TreeNode *f1 = nullptr;
    TreeNode *f2 = nullptr;

    void recoverTree(TreeNode *root) {
        //pre = root;
        pre = new TreeNode(INT_MIN);
        back(root);
        swap(f1->val, f2->val);
    }

    /**
     1,2,3,4,5
     1,4,3,2,5
     */
    void back(TreeNode *node) {
        if (node) {
            back(node->left);
            if (node->val < pre->val && f1 == nullptr) f1 = pre;
            if (node->val < pre->val) f2 = node;
            pre = node;
            back(node->right);
        }
    }

    void show(TreeNode *node){
        if (node) {
            show(node->left);
            cout << node->val << ",";
            show(node->right);
        }
    }

    TreeNode *init() {
        TreeNode *n1 = new TreeNode(1);
        TreeNode *n2 = new TreeNode(2);
        TreeNode *n3 = new TreeNode(3);
        TreeNode *n4 = new TreeNode(4);
        TreeNode *n5 = new TreeNode(5);
        n3->left = n4;
        n4->left = n1;
        n3->right = n2;
        n2->right = n5;

        return n3;
    }
};


int main() {
    Solution so;
    TreeNode *head = so.init();
    so.show(head);
    cout << endl;
    so.recoverTree(head);
    so.show(head);
    cout << endl;
    return 0;
}
